Koryŏ Hangkong được thành lập năm 1954 với tên ban đầu là Chosonminhang (조선민항, 朝鮮民航, Triều Tiên Dân hàng) với tư cách là người kế tục của SOKAO - hãng hàng không liên doanh Liên Xô-CHDCND Triều Tiên thành lập năm 1950[1]. Hãng bắt đầu hoạt động từ ngày 21.9.1955 với các máy bay loại Lisunov Li-2, Antonov An-2 và Ilyushin Il-12. Thập niên 1960 hãng có thêm máy bay Ilyushin Il-14 và Ilyushin Il-18 tua-bin cánh quạt. Năm 1975 hãng có máy bay phản lực Tupolev Tu-154 để phục vụ tuyến Bình Nhưỡng - Đông Berlin - Praha - Moscow. Tuy nhiên Tu-154 không đủ tầm hoạt động xa, nên phải đáp xuống các sân bay trung chuyển ở Irkutsk và Novosibirsk (Nga). Cũng trong thời gian này hãng có thêm các máy bay Tu-134 và An-24 để phục vụ các tuyến bay quốc nội. Năm 1982, hãng có máy bay Ilyushin Il-62 đầu tiên, cho phép bay thẳng từ Bình Nhưỡng tới Moskva.

Kết thúc cuộc Chiến tranh Lạnh và sự sụp đổ của Chủ nghĩa cộng sản ở Đông Âu khiến cho số lớn các tuyến bay quốc tế của hãng phải cắt giảm. Năm 1993 CAAK đổi tên thành Air Koryo. Cùng năm hãng đặt mua 3 máy bay Ilyushin Il-76 để chở hàng hóa tới Trung Quốc và Nga. Mới dây hãng đã đặt mua 2 máy bay Tu-204 để thay đội máy bay quốc tế cũ và cũng bắt đầu hiện đại hóa đội máy bay quốc nội.